সর্টিং অ্যালগরিদম (Sorting Algorithms)

সর্টিং অ্যালগরিদমগুলো ডেটাসেটের উপাদানগুলোকে একটি নির্দিষ্ট ক্রমে সাজানোর জন্য ব্যবহৃত হয়। সর্টিংয়ের মাধ্যমে ডেটাসেটের উপাদানগুলো ক্রমানুসারে (ascending) বা অবতরণক্রমে (descending) সাজানো যায়। এর মাধ্যমে ডেটা খুঁজে পাওয়া সহজ হয় এবং অন্যান্য অপারেশনও দ্রুত করা যায়। এখানে কিছু গুরুত্বপূর্ণ সর্টিং অ্যালগরিদম সম্পর্কে আলোচনা করা হলো:

১. বাবল সর্ট (Bubble Sort)

বাবল সর্ট একটি সহজ কিন্তু ধীরগতির সর্টিং অ্যালগরিদম। এতে প্রতিটি উপাদানকে তার পরবর্তী উপাদানের সাথে তুলনা করা হয় এবং বড় উপাদানটি পরে আসে।

কাজের ধাপ:

1. প্রথম উপাদান থেকে শুরু করে একটির সাথে অন্যটি তুলনা করে বড় উপাদানকে শেষে নিয়ে যাওয়া হয়।
2. প্রতিটি পাস শেষে সবচেয়ে বড় উপাদানটি শেষে চলে যায়।
3. এই প্রক্রিয়া পুনরাবৃত্তি করা হয় যতক্ষণ না সব উপাদান সর্ট হয়ে যায়।

টাইম কমপ্লেক্সিটি: O(n^2)

২. সিলেকশন সর্ট (Selection Sort)

সিলেকশন সর্টে প্রতিটি পাসে সবচেয়ে ছোট (অথবা বড়) উপাদানটি খুঁজে নিয়ে অ্যারের শুরুতে স্থাপন করা হয়। এভাবে প্রতিটি পাসে উপাদানগুলোর ক্রমধারাবাহিকভাবে স্থান পরিবর্তন ঘটে।

কাজের ধাপ:

1. প্রথমে পুরো অ্যারের মধ্যে সবচেয়ে ছোট উপাদানটি খুঁজে বের করে প্রথম স্থানে নিয়ে আসা হয়।
2. এরপর পরবর্তী পজিশনে (second smallest) ছোট উপাদান নিয়ে আসা হয়।
3. এভাবে প্রতিটি পাসে ক্রমানুসারে সর্টিং সম্পন্ন হয়।

টাইম কমপ্লেক্সিটি: O(n^2)

৩. ইনসার্শন সর্ট (Insertion Sort)

ইনসার্শন সর্টে উপাদানগুলো একটি নির্দিষ্ট স্থানে সঠিকভাবে ইনসার্ট করা হয়, যেন সব উপাদান সর্টেড থাকে। এটি ছোট ডেটাসেটের জন্য বেশ কার্যকরী।

কাজের ধাপ:

1. প্রথম উপাদান থেকে শুরু করে পরবর্তী উপাদানগুলোর স্থান নির্ধারণ করে ক্রমানুসারে ইনসার্ট করা হয়।
2. প্রতিটি উপাদানকে তার সঠিক অবস্থানে স্থাপন করা হয়।
3. এভাবে সব উপাদান সর্টেড হয়ে যায়।

টাইম কমপ্লেক্সিটি: O(n^2)

৪. মার্জ সর্ট (Merge Sort)

মার্জ সর্ট একটি ডিভাইড অ্যান্ড কনকার (Divide and Conquer) পদ্ধতি যা ডেটাসেটকে দুটি ভাগে বিভক্ত করে সর্ট করে আবার মার্জ করে।

কাজের ধাপ:

1. ডেটাসেটকে অর্ধেক করে বিভক্ত করা হয়।
2. প্রতিটি অর্ধেককে রিকার্সিভলি সর্ট করা হয়।
3. সর্টেড উপাদানগুলোকে মার্জ করে চূড়ান্ত সর্টেড আউটপুট পাওয়া যায়।

টাইম কমপ্লেক্সিটি: O(n log n)

৫. কুইক সর্ট (Quick Sort)

কুইক সর্টও একটি ডিভাইড অ্যান্ড কনকার পদ্ধতি, যেখানে পিভট (pivot) নামক একটি উপাদান ব্যবহার করে ডেটাসেটকে ছোট ও বড় অংশে ভাগ করা হয়। এটি মার্জ সর্টের চেয়ে কম মেমোরি ব্যবহার করে।

কাজের ধাপ:

1. পিভট হিসেবে একটি উপাদান নির্বাচন করা হয়।
2. পিভটের চেয়ে ছোট উপাদানগুলো বাম দিকে এবং বড় উপাদানগুলো ডান দিকে স্থানান্তর করা হয়।
3. রিকার্সিভলি এই প্রক্রিয়া চালিয়ে পুরো ডেটাসেট সর্ট করা হয়।

টাইম কমপ্লেক্সিটি: গড়ে O(n log n), কিন্তু খারাপ ক্ষেত্রে O(n^2)

৬. হীপ সর্ট (Heap Sort)

হীপ সর্ট একটি কমপ্লিট বাইনারি ট্রি (Complete Binary Tree) ব্যবহার করে কাজ করে, যেখানে ডেটাসেটকে হীপ ডেটা স্ট্রাকচারে রূপান্তরিত করা হয় এবং প্রতিবার মেক্স হীপ (Max Heap) অথবা মিন হীপ (Min Heap) থেকে উপাদান তুলে আনা হয়।

কাজের ধাপ:

1. ডেটাসেটকে মেক্স হীপ বা মিন হীপে রূপান্তরিত করা হয়।
2. প্রতিটি উপাদানকে ক্রমানুসারে তুলে সর্ট করা হয়।
3. এই প্রক্রিয়া অব্যাহত থাকে যতক্ষণ না সব উপাদান সর্টেড হয়।

টাইম কমপ্লেক্সিটি: O(n log n)

৭. র‌্যাডিক্স সর্ট (Radix Sort)

র‌্যাডিক্স সর্ট এমন ডেটাসেটের জন্য কার্যকরী যেগুলো সংখ্যায়িত বা কারেক্টার (অক্ষর) ডেটাসেট। এটি সংখ্যার স্থানিক মান ব্যবহার করে কাজ করে।

কাজের ধাপ:

1. লেসট সিগনিফিকেন্ট ডিজিট (LSD) থেকে শুরু করে প্রতিটি ডিজিট অনুযায়ী সর্ট করা হয়।
2. প্রতিটি ডিজিটের জন্য একাধিক পাস চালানো হয় যতক্ষণ না সব উপাদান সর্টেড হয়।

টাইম কমপ্লেক্সিটি: O(d*(n + b)) , যেখানে d ডিজিট সংখ্যা এবং b হল বেস (আধার)।

তুলনা:

প্রতিটি সর্টিং অ্যালগরিদমের নিজস্ব সুবিধা ও অসুবিধা আছে। ডেটাসেটের আকার, গঠন, এবং সার্টিংয়ের শর্ত অনুযায়ী উপযুক্ত অ্যালগরিদম নির্বাচন করা উচিত।

বেসিক সর্টিং অ্যালগরিদমগুলি হল প্রাথমিক এবং সহজ সর্টিং পদ্ধতি, যা ছোট ডেটাসেটের জন্য বেশ উপযোগী। এখানে Bubble Sort, Selection Sort, এবং Insertion Sort-এর কাজের পদ্ধতি এবং তাদের টাইম কমপ্লেক্সিটি নিয়ে আলোচনা করা হলো।

১. বাবল সর্ট (Bubble Sort)

Bubble Sort একটি সহজ সর্টিং অ্যালগরিদম, যেখানে তালিকার প্রতিটি উপাদান পর্যায়ক্রমে তুলনা করা হয় এবং প্রয়োজন অনুযায়ী তাদের বিনিময় করা হয়। এটি ধীরে ধীরে সবচেয়ে বড় উপাদানগুলিকে তালিকার শেষে নিয়ে যায়, ঠিক বুদবুদের মতো।

অ্যালগরিদমের প্রক্রিয়া:

1. প্রথম ইনডেক্স থেকে শুরু করে প্রতিটি উপাদান পরবর্তী উপাদানের সাথে তুলনা করা হয়।
2. যদি প্রথমটি পরেরটির চেয়ে বড় হয়, তাহলে তারা স্থান বিনিময় করে।
3. এই প্রক্রিয়াটি বারবার চলতে থাকে যতক্ষণ না তালিকার সমস্ত উপাদান সর্ট হয়ে যায়।

টাইম কমপ্লেক্সিটি:

• Best Case: O(n) (যদি তালিকাটি আগে থেকেই সর্টেড থাকে)
• Worst and Average Case: O(n^2)

উদাহরণ:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap
    return arr

২. সিলেকশন সর্ট (Selection Sort)

Selection Sort অ্যালগরিদমটি তালিকার প্রতিটি পজিশনে সবচেয়ে ছোট উপাদানটি খুঁজে এনে রাখে। এটি প্রথম পজিশনে সবচেয়ে ছোট উপাদানটি রাখে, তারপর দ্বিতীয় পজিশনে দ্বিতীয় ছোট উপাদান রাখে এবং এভাবে সর্টিং সম্পন্ন করে।

অ্যালগরিদমের প্রক্রিয়া:

1. প্রথমে সম্পূর্ণ তালিকা থেকে সবচেয়ে ছোট উপাদানটি খুঁজে বের করে প্রথম পজিশনে আনা হয়।
2. দ্বিতীয় পজিশনে পরবর্তী সবচেয়ে ছোট উপাদান খুঁজে এনে স্থাপন করা হয়।
3. এভাবে প্রতিটি পজিশনে যথাক্রমে ছোট উপাদানগুলি রাখে যতক্ষণ না তালিকাটি সর্ট হয়ে যায়।

টাইম কমপ্লেক্সিটি:

• Best, Worst, and Average Case: O(n^2) (এটি প্রতিটি ক্ষেত্রে একই থাকে)

উদাহরণ:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # Swap
    return arr

৩. ইনসার্শন সর্ট (Insertion Sort)

Insertion Sort তালিকার প্রতিটি উপাদানকে সঠিক পজিশনে ইনসার্ট করে সর্ট করে। এই অ্যালগরিদমটি প্রথমে একটি উপাদান নিয়ে তার স্থান নির্ধারণ করে এবং পরে পরবর্তী উপাদানগুলিকে ক্রমানুসারে তাদের সঠিক অবস্থানে ইনসার্ট করে সর্টিং সম্পন্ন করে।

অ্যালগরিদমের প্রক্রিয়া:

1. দ্বিতীয় উপাদান থেকে শুরু করে প্রতিটি উপাদানকে তার সঠিক স্থানে ইনসার্ট করা হয়।
2. ইনসার্ট করতে প্রথমে সঠিক পজিশন খুঁজে বের করা হয় এবং সেখানে উপাদানটিকে স্থাপন করা হয়।
3. এই প্রক্রিয়াটি তালিকার শেষ পর্যন্ত চালানো হয়।

টাইম কমপ্লেক্সিটি:

• Best Case: O(n) (যদি তালিকাটি আগে থেকেই সর্টেড থাকে)
• Worst and Average Case: O(n^2)

উদাহরণ:

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

তুলনা

এই তিনটি সর্টিং অ্যালগরিদম সাধারণত ছোট ডেটাসেট এবং শিক্ষণমূলক উদাহরণ হিসেবে ব্যবহৃত হয়। বড় ডেটাসেটের জন্য এগুলো কম কার্যকর, তাই বড় ডেটাসেটে Merge Sort বা Quick Sort এর মতো আরও কার্যকর অ্যালগরিদম ব্যবহৃত হয়।

অ্যাডভান্সড সর্টিং অ্যালগরিদমগুলো বড় ডেটাসেটকে দ্রুত ও কার্যকরভাবে সাজানোর জন্য ব্যবহৃত হয়। এখানে আমরা Merge Sort, Quick Sort, এবং Heap Sort সম্পর্কে বিস্তারিত আলোচনা করব।

১. Merge Sort

Merge Sort একটি ডিভাইড-অ্যান্ড-কনকার (Divide and Conquer) ভিত্তিক অ্যালগরিদম যা অ্যারেকে দুই ভাগে বিভক্ত করে, তারপর প্রতিটি অংশকে রিকার্সিভভাবে সর্ট করে এবং শেষ পর্যন্ত উভয় অংশকে মিলে একটি সর্টেড অ্যারে তৈরি করে।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: O(n log n) সর্বদা
• স্পেস কমপ্লেক্সিটি: O(n), কারণ অতিরিক্ত মেমোরি প্রয়োজন হয়
• স্থায়িত্ব: স্ট্যাবল, কারণ এটি সমমানের উপাদানের ক্রম ঠিক রাখে

উদাহরণ কোড (Swift):

func mergeSort(arr: [Int]) -> [Int] {
    if arr.count <= 1 { return arr }
    
    let mid = arr.count / 2
    let left = mergeSort(arr: Array(arr[..<mid]))
    let right = mergeSort(arr: Array(arr[mid...]))
    
    return merge(left, right)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var mergedArr = [Int]()
    var i = 0, j = 0
    
    while i < left.count && j < right.count {
        if left[i] < right[j] {
            mergedArr.append(left[i])
            i += 1
        } else {
            mergedArr.append(right[j])
            j += 1
        }
    }
    
    return mergedArr + left[i...] + right[j...]
}

কিভাবে কাজ করে:

1. অ্যারেকে মধ্যবিন্দু থেকে দুই ভাগে বিভক্ত করে।
2. প্রতিটি ভাগকে আলাদাভাবে সর্ট করে।
3. অবশেষে, দুটি সর্ট করা ভাগ মিলে একটি পুরোপুরি সর্টেড অ্যারে তৈরি করে।

২. Quick Sort

Quick Sort আরেকটি ডিভাইড-অ্যান্ড-কনকার অ্যালগরিদম যা পিভট (Pivot) বাছাই করে অ্যারেকে ভাগ করে এবং প্রতিটি অংশকে সর্ট করে। এর প্রধান সুবিধা হলো এটি সাধারণত ইন-প্লেস সর্টিং করে, অর্থাৎ অতিরিক্ত মেমোরি প্রয়োজন হয় না।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: গড়ে O(n log n), তবে খারাপ ক্ষেত্রে O(n^2) হতে পারে (যদি সব সময় খারাপ পিভট বাছাই হয়)
• স্পেস কমপ্লেক্সিটি: O(log n) ইন-প্লেস, অর্থাৎ অতিরিক্ত মেমোরি লাগে না।
• স্থায়িত্ব: আনস্ট্যাবল, কারণ সমমানের উপাদানগুলোর ক্রম পরিবর্তিত হতে পারে

উদাহরণ কোড (Swift):

func quickSort(arr: inout [Int], low: Int, high: Int) {
    if low < high {
        let pivotIndex = partition(&arr, low: low, high: high)
        quickSort(arr: &arr, low: low, high: pivotIndex - 1)
        quickSort(arr: &arr, low: pivotIndex + 1, high: high)
    }
}

func partition(_ arr: inout [Int], low: Int, high: Int) -> Int {
    let pivot = arr[high]
    var i = low
    
    for j in low..<high {
        if arr[j] <= pivot {
            arr.swapAt(i, j)
            i += 1
        }
    }
    arr.swapAt(i, high)
    return i
}

কিভাবে কাজ করে:

1. একটি পিভট এলিমেন্ট নির্বাচন করে।
2. অ্যারের উপাদানগুলোকে পিভটের চারপাশে পুনর্বিন্যাস করে, যাতে পিভটের বামে ছোট উপাদান এবং ডানে বড় উপাদান থাকে।
3. রিকার্সিভভাবে প্রতিটি অংশকে সর্ট করে।

৩. Heap Sort

Heap Sort একটি কমপ্লিট বাইনারি ট্রি ব্যবহার করে সর্টিং করে, যেখানে প্রতিটি নোড তার চাইল্ড নোড থেকে বড় বা ছোট হয়। এটি মূলত ম্যাক্স-হিপ বা মিন-হিপ ব্যবহার করে একটি সর্টেড অ্যারে তৈরি করে।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: সর্বদা O(n log n)
• স্পেস কমপ্লেক্সিটি: O(1), কারণ এটি ইন-প্লেস সর্টিং করে
• স্থায়িত্ব: আনস্ট্যাবল, কারণ উপাদানগুলোর ক্রম পরিবর্তিত হতে পারে

উদাহরণ কোড (Swift):

func heapSort(arr: inout [Int]) {
    let n = arr.count
    
    // Build max heap
    for i in stride(from: n / 2 - 1, through: 0, by: -1) {
        heapify(&arr, n, i)
    }
    
    // Extract elements from heap one by one
    for i in stride(from: n - 1, through: 1, by: -1) {
        arr.swapAt(0, i)  // Move current root to end
        heapify(&arr, i, 0)
    }
}

func heapify(_ arr: inout [Int], _ n: Int, _ i: Int) {
    var largest = i
    let left = 2 * i + 1
    let right = 2 * i + 2
    
    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        arr.swapAt(i, largest)
        heapify(&arr, n, largest)
    }
}

কিভাবে কাজ করে:

1. প্রথমে অ্যারেকে একটি ম্যাক্স হিপে রূপান্তরিত করে।
2. তারপর হিপ থেকে এলিমেন্টগুলো সরিয়ে একটি সর্টেড অ্যারে তৈরি করে। প্রতিটি ধাপে সর্বোচ্চ মানের এলিমেন্টটি হিপ থেকে সরানো হয় এবং হিপকে পুনর্গঠিত করা হয়।

উপসংহার

এই তিনটি অ্যাডভান্সড সর্টিং অ্যালগরিদম বিভিন্ন পরিস্থিতিতে উপযোগী:

• Merge Sort: যখন স্থায়িত্ব প্রয়োজন এবং O(n log n) নিশ্চিত দরকার।
• Quick Sort: সাধারণত দ্রুততম, তবে খারাপ ক্ষেত্রে O(n^2) হয়ে যেতে পারে।
• Heap Sort: ইন-প্লেস এবং সর্বদা O(n log n), তবে স্থায়িত্ব নেই।

এগুলো নির্বাচন প্রয়োজনীয়তাভেদে করা হয় এবং প্রতিটি অ্যালগরিদমের নিজস্ব কিছু সুবিধা ও সীমাবদ্ধতা রয়েছে।

টাইম কমপ্লেক্সিটি এবং স্পেস কমপ্লেক্সিটি বিশ্লেষণ একটি অ্যালগরিদমের কার্যকারিতা মূল্যায়নের দুটি গুরুত্বপূর্ণ দিক। টাইম কমপ্লেক্সিটি নির্দেশ করে একটি অ্যালগরিদম কত দ্রুত কাজ সম্পন্ন করে, আর স্পেস কমপ্লেক্সিটি নির্দেশ করে কাজটি সম্পন্ন করতে কতটুকু মেমোরি ব্যবহার করা হয়।

টাইম কমপ্লেক্সিটি (Time Complexity)

টাইম কমপ্লেক্সিটি নির্দেশ করে একটি অ্যালগরিদমের কত সময় লাগবে, ইনপুট আকারের ভিত্তিতে। আমরা সাধারণত Big O নোটেশন ব্যবহার করে টাইম কমপ্লেক্সিটি প্রকাশ করি, যা আমাদের worst-case সিনারিওতে ইনপুট আকার বৃদ্ধি পাওয়ার সাথে সাথে টাইম কমপ্লেক্সিটির বৃদ্ধি নির্দেশ করে।

টাইম কমপ্লেক্সিটির সাধারণ ধরনগুলো:

O(1): এটি কনস্ট্যান্ট টাইম কমপ্লেক্সিটি। ইনপুট আকার যাই হোক, এটি সবসময় নির্দিষ্ট সময় নেয়। যেমন: একবার অ্যারে থেকে একটি নির্দিষ্ট ইন্ডেক্সের মান অ্যাক্সেস করা।

O(log n): লগারিদমিক টাইম কমপ্লেক্সিটি। ইনপুট আকার দ্বিগুণ হলেও টাইম কমপ্লেক্সিটি ধীরে ধীরে বৃদ্ধি পায়। বাইনারি সার্চের টাইম কমপ্লেক্সিটি O(log n)।

O(n): লিনিয়ার টাইম কমপ্লেক্সিটি। ইনপুট আকার বৃদ্ধির সাথে টাইম কমপ্লেক্সিটিও সরাসরি বৃদ্ধি পায়। যেমন: একটি লিস্টের প্রতিটি আইটেমে লুপ করা।

O(n log n): কিছু অ্যালগরিদম যেমন মার্জ এবং কুইক সর্টের টাইম কমপ্লেক্সিটি O(n log n)।

O(n^2): কোয়াড্রাটিক টাইম কমপ্লেক্সিটি। ইনপুট আকার দ্বিগুণ হলে টাইম কমপ্লেক্সিটি চারগুণ বৃদ্ধি পায়। যেমন: দুটি নেস্টেড লুপ।

O(2^n): এক্সপোনেনশিয়াল টাইম কমপ্লেক্সিটি। ইনপুট আকার বাড়লে টাইম কমপ্লেক্সিটি দ্রুত বেড়ে যায়। এটি অনেক রিকার্সিভ সমস্যায় দেখা যায়।

টাইম কমপ্লেক্সিটি গণনার উদাহরণ: একটি অ্যালগরিদম যদি ইনপুটের প্রতিটি এলিমেন্টে একবার করে কাজ করে, তবে তার টাইম কমপ্লেক্সিটি হবে O(n)O(n)। আর যদি প্রতিটি এলিমেন্টের সাথে পরবর্তী এলিমেন্টের সবগুলো জোড়া চেক করে, তবে টাইম কমপ্লেক্সিটি হবে O(n2)O(n2)।

স্পেস কমপ্লেক্সিটি (Space Complexity)

স্পেস কমপ্লেক্সিটি নির্দেশ করে একটি অ্যালগরিদম কত মেমোরি ব্যবহার করে। এটি প্রধানত দুই ধরনের মেমোরির ব্যবহার নিয়ে আলোচনা করে:

Fixed Space: ইনপুট আকার যাই হোক, কিছু নির্দিষ্ট মেমোরি যা অ্যালগরিদমের জন্য প্রয়োজন হয়। যেমন: কিছু নির্দিষ্ট ভেরিয়েবল, কন্ট্রোল স্ট্রাকচার।

Variable Space: ইনপুট আকারের উপর নির্ভর করে যে মেমোরি প্রয়োজন হয়, যেমন: ডাইনামিক ডাটা স্ট্রাকচার (লিস্ট, ট্রি, স্ট্যাক)।

স্পেস কমপ্লেক্সিটির ধরনগুলো:

• O(1): কনস্ট্যান্ট স্পেস। ইনপুট আকার যাই হোক, মেমোরি ব্যবহার অপরিবর্তিত থাকে।
• O(n): লিনিয়ার স্পেস। ইনপুট আকার অনুযায়ী মেমোরির প্রয়োজনীয়তা বৃদ্ধি পায়।
• O(n^2): কোয়াড্রাটিক স্পেস। ইনপুট আকারের সাথে মেমোরি প্রয়োজন স্কোয়ার অনুপাতে বাড়ে।

স্পেস কমপ্লেক্সিটির উদাহরণ: একটি অ্যালগরিদম যদি শুধুমাত্র কয়েকটি নির্দিষ্ট ভেরিয়েবল ব্যবহার করে, তবে তার স্পেস কমপ্লেক্সিটি হবে O(1)O(1)। তবে যদি একটি লিস্ট বা আরেকটি ডাটা স্ট্রাকচার তৈরি করতে হয় যার আকার ইনপুটের আকারের সমান, তবে স্পেস কমপ্লেক্সিটি হবে O(n)O(n)।

টাইম এবং স্পেস কমপ্লেক্সিটির মধ্যে সম্পর্ক

বেশিরভাগ ক্ষেত্রে, আমরা চাই টাইম এবং স্পেস কমপ্লেক্সিটি কম থাকুক। তবে কখনো কখনো একটি কমপ্লেক্সিটি কম রাখতে গেলে অন্যটি বেশি হয়ে যেতে পারে, যেমন:

• Time-Space Trade-Off: কিছু অ্যালগরিদমের জন্য কম সময়ে কার্য সম্পন্ন করতে বেশি মেমোরি ব্যবহার করতে হয়, আবার কম মেমোরি ব্যবহার করতে হলে বেশি সময় লাগতে পারে।

উদাহরণ: মেমোরি ব্যবহার করে একটি ডেটা স্ট্রাকচারকে কাশিং করলে এটি অনুসন্ধানে কম সময় নেবে। কিন্তু এটি বেশি মেমোরি ব্যবহার করবে।

সারসংক্ষেপে

টাইম কমপ্লেক্সিটি নির্দেশ করে একটি অ্যালগরিদমের সময়িক কার্যকারিতা, আর স্পেস কমপ্লেক্সিটি নির্দেশ করে এর মেমোরি ব্যবহারের কার্যকারিতা। একটি কার্যকর অ্যালগরিদম ডিজাইন করতে উভয় কমপ্লেক্সিটিই গুরুত্বপূর্ণ, এবং তা নির্ভর করে নির্দিষ্ট সমস্যার প্রয়োজনীয়তার উপর।